package 第三周;

/*
 * @author  YxinMiracle
 * @date  2022-04-26 19:22
 * @Gitee: https://gitee.com/yxinmiracle
 */

import java.util.ArrayList;
import java.util.List;

public class 组合 {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        recur(n,1,k,result,new ArrayList<>());
        return result;
    }

    public void recur(int n, int num, int endLength, List<List<Integer>> result, List<Integer> temp) {
        // 剪枝
        if (temp.size() > endLength || temp.size() + (n - num + 1) < endLength){
            return;
        }
        if (n < num){
            if (endLength == temp.size()) {
                List<Integer> list = new ArrayList<>(temp);
                result.add(list);
                return;
            }
            return;
        }

        // 选
        temp.add(num);
        recur(n,num+1,endLength,result,temp);
        temp.remove(temp.size()-1);
        // 不选
        recur(n,num+1,endLength,result,temp);
    }

    public static void main(String[] args) {
        System.out.println(new 组合().combine(4,2));
    }
}
